package leetcode.primary;

import java.util.Arrays;

public class T45 {
    public int jump(int[] nums) {
        if (nums.length==1){
            return 0;
        }
        int length = nums.length;
        int[][] dp = new int[nums.length][nums.length];

        for (int[] ints : dp) {
            Arrays.fill(ints, 1001);
        }


        int jump = 0;
        int prefix =0;
        for(int i =0;i<length;i++){
            for (int j = 0; j < length; j++) {
                if (i>0 && j<=prefix){
                    dp[i][j] = dp[i-1][j];
                }else {
                    jump++;
                    if (i>0){
                        if ( dp[i-1][j]>dp[i][i]+1){
                            jump = dp[i][i]+1;
                            dp[i][j] = jump;
                        }else {
                            dp[i][j] = dp[i-1][j];
                        }
                    }

                    for (;j< length;j++){
                        if (prefix+nums[i]>=j){
                            dp[i][j] = jump;
                        }else {
                            break;
                        }
                    }
                    prefix+=nums[i];
//                    if (j == length){
//
////                        return jump;
//                    }
                    break;
                }
            }
        }

        for (int x = 0; x < dp.length; x++) {
            for (int k = 0; k < dp[x].length; k++) {
                System.out.print(dp[x][k]+" ");
            }
            System.out.println();
        }
        return jump;
    }

    public static void main(String[] args) {
        T45 test = new T45();
        int jump = test.jump(new int[]{2,1,1,1,1});
        System.out.println(jump);
    }
}
